Maximum Independent Set

释义 Definition

最大独立集：在图论中，独立集指图中一组顶点，任意两点之间都没有边相连；最大独立集（maximum independent set）是指在所有独立集中，顶点数量最多的那个（或那些）。该问题在一般图上是经典的计算难题（常见于算法与复杂性讨论）。

例句 Examples

We need to find a maximum independent set in this graph.
我们需要在这张图中找出一个最大独立集。

Finding a maximum independent set is NP-hard, so we often use approximation or heuristics for large networks.
寻找最大独立集是 NP-难问题，因此在大型网络中我们常用近似算法或启发式方法。

发音 Pronunciation (IPA)

/ˈmæksɪməm ˌɪndɪˈpɛndənt sɛt/

词源 Etymology

该术语由三部分构成：maximum（最大） + independent（独立的） + set（集合）。其中“independent set（独立集）”源自图论对“互不相邻的顶点集合”的命名；加上“maximum”表示在所有满足条件的集合中取规模最大的。在中文里通常译为“最大独立集”，与“最大团（maximum clique）”等术语形成对照（两者在补图意义下密切相关）。

相关词 Related Words

• Independent
• Set
• Graph
• Vertex
• Edge
• Independent Set
• Maximum Clique
• NP-Hard
• Approximation
• Heuristic

文学与经典著作 Literary Works

• Computers and Intractability: A Guide to the Theory of NP-Completeness（Michael R. Garey, David S. Johnson）——将最大独立集作为经典 NP-完全/NP-难问题相关内容讨论。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——在图算法与复杂性相关章节/习题中常提及独立集及其困难性。
• Algorithm Design（Jon Kleinberg, Éva Tardos）——在近似算法、图问题建模等语境下常出现最大独立集或相关变体。